//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "iterator_traits.h"
#include "type_traits.h"
#include "utility.h"
#include "functional.h"
#include "algobase.h"


FC_NAMESPACE_BEGIN


// search.h (non-modifying sequence operations)
//
// all_of
// any_of
// none_of
// for_each
// count
// count_if
// mismatch
// equal
// find					(algobase.h)
// find_if				(algobase.h)
// find_if_not
// find_end
// find_first_of
// find_first_not_of
// find_last_of
// find_last_not_of
// adjacent_find
// search
// search_n



// all_of

template <class InputIterator, class UnaryPredicate> inline
	bool all_of( InputIterator first, InputIterator last, UnaryPredicate predicate )
	{
		for( ; first != last; ++first )
			if( !predicate(*first) )
				return false;
		return true;
	}


// any_of

template <class InputIterator, class UnaryPredicate> inline
	bool any_of( InputIterator first, InputIterator last, UnaryPredicate predicate )
	{
		for( ; first != last; ++first )
			if( predicate(*first) )
				return true;
		return false;
	}


// none_of

template <class InputIterator, class UnaryPredicate> inline
	bool none_of( InputIterator first, InputIterator last, UnaryPredicate predicate )
	{
		for( ; first != last; ++first )
			if( predicate(*first) )
				return false;
		return true;
	}


// for_each

template <class InputIterator, class UnaryFunction> inline
	void for_each( InputIterator first, InputIterator last, UnaryFunction function )
	{
		for( ; first != last; ++first )
			function(*first);
	}


// count

template <class InputIterator, class T> inline
	size_t count( InputIterator first, InputIterator last, const T& value )
	{
		size_t result = 0;
		for( ; first != last; ++first )
			if( *first == value )
				++result;

		return result;
	}


// count_if

template <class InputIterator, class UnaryPredicate> inline
	size_t count_if( InputIterator first, InputIterator last, UnaryPredicate predicate )
	{
		size_t result = 0;
		for( ; first != last; ++first )
			if( predicate(*first) )
				++result;

		return result;
	}


// mismatch

template <class InputIterator, class BinaryPredicate> inline
	pair<InputIterator, InputIterator>
	mismatch( InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate predicate )
	{
		while( first1 != last1 && predicate(*first1, *first2) )
			++first1, ++first2;

		return pair<InputIterator, InputIterator>(first1, first2);
	}

template <class InputIterator> inline
	pair<InputIterator, InputIterator> mismatch( InputIterator first1, InputIterator last1, InputIterator first2 )
	{
		while( first1 != last1 && *first1 == *first2 )
			++first1, ++first2;

		return pair<InputIterator, InputIterator>(first1, first2);
	}


// equal

template <class InputIterator1, class InputIterator2, class BinaryPredicate> inline
	bool equal( InputIterator1 first, InputIterator1 last, InputIterator2 first2, BinaryPredicate predicate )
	{
 		for( ; first != last; ++first, ++first2 )
			if( !predicate(*first, *first2) )
				return false;
		return true;
	}

template <class InputIterator1, class InputIterator2> inline
	bool equal( InputIterator1 first, InputIterator1 last, InputIterator2 first2 )
	{
 		for( ; first != last; ++first, ++first2 )
			if( !(*first == *first2) )
				return false;
		return true;
	}


// find_if_not

template<class InputIterator, class UnaryPredicate>
	InputIterator find_if_not( InputIterator first, InputIterator last, UnaryPredicate predicate )
	{
		while( (first != last) && predicate(*first) )
			++first;
		return first;
	}


// find_first_of

template <class ForwardIterator1, class ForwardIterator2> inline
	ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2 )
	{
		for( ForwardIterator2 i; first1 != last1; ++first1 )
		{
			for( i = first2; i != last2; ++i )
			{
				if( *first1 == *i )
					return first1;
			}
		}

		return last1;
	}

template <class ForwardIterator, class T> inline
	ForwardIterator find_first_of( ForwardIterator first, ForwardIterator last, const T& value )
	{
		return find(first, last, value);
	}


// find_first_not_of

template <class ForwardIterator1, class ForwardIterator2> inline
	ForwardIterator1 find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2 )
	{
		for( ForwardIterator2 i; first1 != last1; ++first1 )
		{
			for( i = first2; i != last2; ++i )
			{
				if( *i == *first1 )
					break;
			}
			if( i == last2 )
				return first1;
		}

		return first1;
	}

template <class ForwardIterator, class T> inline
	ForwardIterator find_first_not_of( ForwardIterator first, ForwardIterator last, const T& value )
	{
		while( first != last && *first == value ) ++first;
		return first;
	}


// find_last_of

template <class BidirectionalIterator1, class BidirectionalIterator2> inline
	BidirectionalIterator1 find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
	BidirectionalIterator2 first2, BidirectionalIterator2 last2 )
	{
		while( first1 != last1 )
		{
			--last1;
			for( BidirectionalIterator2 i = first2; i != last2; ++i )
			{
				if( *i == *last1 )
					return last1;
			}
		}

		return first1;
	}

template <class BidirectionalIterator, class T> inline
	BidirectionalIterator find_last_of( BidirectionalIterator first, BidirectionalIterator last, const T& value )
	{
		while( first != last && *--last != value ) ;
		return last;
	}


// find_last_not_of

template <class BidirectionalIterator1, class BidirectionalIterator2> inline
	BidirectionalIterator1 find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
	BidirectionalIterator2 first2, BidirectionalIterator2 last2 )
	{
		BidirectionalIterator2 i;
		while( first1 != last1 )
		{
			--last1;
			for( i = first2; i != last2; ++i )
			{
				if( *i == *last1 )
					break;
			}
			if( i == last2 )
				return last1;
		}

		return first1;
	}

template <class BidirectionalIterator, class T> inline
	BidirectionalIterator find_last_not_of( BidirectionalIterator first, BidirectionalIterator last, const T& value )
	{
		while( first != last && *--last == value ) ;
		return last;
	}


// adjacent_find

template <class ForwardIterator, class BinaryPredicate> inline
	ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last, BinaryPredicate predicate )
	{
		if( FC_LIKELY(first != last) )
		{
			ForwardIterator next = first;
			++next;
			while( next != last )
			{
				if( predicate(*first, *next) )
					return first;

				first = next;
				++next;
			}
		}
		return last;
	}

template <class ForwardIterator> inline
	ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last )
	{
		if( FC_LIKELY(first != last) )
		{
			ForwardIterator next = first;
			++next;
			while( next != last )
			{
				if( *first == *next )
					return first;

				first = next;
				++next;
			}
		}
		return last;
	}



namespace internal
{
	// search

	template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> inline
	ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate predicate,
	forward_iterator_tag, forward_iterator_tag )
	{
		if( FC_UNLIKELY(first2 == last2) )
			return first1;

		ForwardIterator1 a;
		ForwardIterator2 b;

		while( first1 != last1 )
		{
			// find next occurance of first value in sequence
			while( first1 != last1 && !predicate(*first1, *first2) )
				++first1;

			if( first1 != last1 )
			{
				a = first1;
				b = first2;

				do {
					if( ++a == last1 ) return last1;
					if( ++b == last2 ) return first1;
				} while( predicate(*a, *b) );

				++first1;
			}
		}

		return last1;
	}

	template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate> inline
	RandomAccessIterator1 search( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
	RandomAccessIterator2 first2, RandomAccessIterator2 last2, BinaryPredicate predicate,
	random_access_iterator_tag, random_access_iterator_tag )
	{
		typedef typename fc::iterator_traits<RandomAccessIterator1>::difference_type difference_type1;
		typedef typename fc::iterator_traits<RandomAccessIterator2>::difference_type difference_type2;
		const difference_type1 dist1 = difference_type1(last1 - first1);
		const difference_type2 dist2 = difference_type2(last2 - first2);

		if( FC_UNLIKELY(dist2 == 0) )
			return first1;

		if( FC_LIKELY(!(dist1 < dist2)) )
		{
			const RandomAccessIterator1 endFirst = last1 - dist2;
			for( ; first1 != endFirst; ++first1 )
			{
				if( predicate(*first1, *first2) )
				{
					RandomAccessIterator1 a = first1 + 1;
					RandomAccessIterator2 b = first2 + 1;
					for( ; ; ++a, ++b )
					{
						if( b == last2 )
							return first1; // match found

						if( !predicate(*a, *b) )
							break;
					}
				}
			}
		}

		return last1;
	}

} //internal


template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> inline
	ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate predicate )
	{
		return internal::search<ForwardIterator1, ForwardIterator2, BinaryPredicate>( first1, last1, first2, last2, predicate,
			typename iterator_traits<ForwardIterator1>::iterator_type(),
			typename iterator_traits<ForwardIterator2>::iterator_type()
		);
	}

template <class ForwardIterator1, class ForwardIterator2> inline
	ForwardIterator1 search( ForwardIterator1 first1, ForwardIterator1 last1,
	ForwardIterator2 first2, ForwardIterator2 last2 )
	{
		return internal::search( first1, last1, first2, last2, equal_to< typename iterator_traits<ForwardIterator1>::value_type >(),
			typename iterator_traits<ForwardIterator1>::iterator_type(),
			typename iterator_traits<ForwardIterator2>::iterator_type()
		);
	}


// reverse_search

//template <class BidirectionalIterator1, class BidirectionalIterator2, class BinaryPredicate> inline
//	BidirectionalIterator1 reverse_search( BidirectionalIterator1 first1, BidirectionalIterator1 last1,
//	BidirectionalIterator2 first2, BidirectionalIterator2 last2, BinaryPredicate predicate )


namespace internal
{
	// search_n

	template <class ForwardIterator, class Size, class T, class BinaryPredicate> inline
	ForwardIterator search_n( ForwardIterator first, ForwardIterator last,
	Size n, const T& value, BinaryPredicate predicate, forward_iterator_tag )
	{
		while( first != last )
		{
			if( predicate(*first, value) )
			{
				ForwardIterator f = first;
				Size i;
				for( i = 1; i < n; ++i )
				{
					if( ++first == last || !predicate(*first, value) )
						break;
				}
				if( i == n )
					return f;
			}
			else ++first;
		}

		return last;
	}

	// Much faster version of search_n which we can specialize
	// for random access iterators.

	template <class RandomAccessIterator, class Size, class T, class BinaryPredicate> inline
	RandomAccessIterator search_n( RandomAccessIterator first,
	RandomAccessIterator last, Size n, const T& value, BinaryPredicate predicate, random_access_iterator_tag )
	{
		if( n < 2 )
			return fc::find(first, last, value);

		Size skip = (n - 1);
		Size remainder;
		RandomAccessIterator lookAhead = first + skip;
		RandomAccessIterator backTrack;

		for( ; lookAhead < last; lookAhead += n )
		{
			if( predicate(*lookAhead, value) )
			{
				remainder = skip;
				for( backTrack = lookAhead - 1; predicate(*backTrack, value); --backTrack )
				{
					if( --remainder == 0 )
						return (lookAhead - skip);
				}

				while( *(++lookAhead) == value )
				{
					if( --remainder == 0 )
						return (lookAhead - skip);
				}

				// no match found and lookAhead is already optimally placed at
				// end of tested range, so do nothing.
			}
		}

		return last;
	}

	template <class ForwardIterator, class Size, class T> inline
	ForwardIterator search_n( ForwardIterator first, ForwardIterator last,
	Size n, const T& value, forward_iterator_tag )
	{
		while( first != last )
		{
			if( *first == value )
			{
				ForwardIterator f = first;
				Size i;
				for( i = 1; i < n; ++i )
				{
					if( ++first == last || !(*first == value) )
						break;
				}
				if( i == n )
					return f;
			}
			else ++first;
		}

		return last;
	}


	// Much faster version of search_n which we can specialize
	// for random access iterators.

	template <class RandomAccessIterator, class Size, class T> inline
	RandomAccessIterator search_n( RandomAccessIterator first,
	RandomAccessIterator last, Size n, const T& value, random_access_iterator_tag )
	{
		if( n < 2 )
			return fc::find(first, last, value);

		Size skip = (n - 1);
		Size remainder;
		RandomAccessIterator lookAhead = first + skip;
		RandomAccessIterator backTrack;

		for( ; lookAhead < last; lookAhead += n )
		{
			if( *lookAhead == value )
			{
				remainder = skip;
				for( backTrack = lookAhead - 1; *backTrack == value; --backTrack )
				{
					if( --remainder == 0 )
						return (lookAhead - skip);
				}

				while( *(++lookAhead) == value )
				{
					if( --remainder == 0 )
						return (lookAhead - skip);
				}

				// no match found and lookAhead is already optimally placed at
				// end of tested range, so do nothing.
			}
		}

		return last;
	}

}



// search_n

template <class InputIterator, class Size, class T, class BinaryPredicate> FC_FORCE_INLINE
	InputIterator search_n( InputIterator first, InputIterator last, Size n, const T& value, BinaryPredicate predicate )
	{
		return internal::search_n( first, last, n, value, predicate,
			typename iterator_traits<InputIterator>::iterator_type() );
	}

template <class InputIterator, class Size, class T> FC_FORCE_INLINE
	InputIterator search_n( InputIterator first, InputIterator last, Size n, const T& value )
	{
		return internal::search_n( first, last, n, value,
			typename iterator_traits<InputIterator>::iterator_type() );
	}




FC_NAMESPACE_END

